package f_graph_basics.a_graph_representation;

import java.util.ArrayList;

/**
 * sparse graph 邻接表 实现 稀疏图
 * 缺点：
 * 1.添加边的时候，为了提高性能一般不判断平行边 - 即允许平行边
 * 优点：
 * 1.稀疏图中遍历邻边的时候效率极高，由于其他算法很多依赖遍历邻边的操作，所以处理非完全图时整体性能会更好
 * 2.邻边遍历的顺序就是添加邻边的顺序
 */
public class SparseGraph implements Graph{

    private int v; // vertex 顶点
    private int e; // edge 边
    private boolean isDirected; // 是否是有向图
    private ArrayList<Integer>[] g; // list graph 邻接表 - 稀疏图

    /**
     * 构造函数 - 构造一个以v为顶点数的空图（没有边）
     * eg. v为4的邻接表
     * 0 ——> 1
     * 1 ——> 0
     * 2 ——> 3
     * 3 ——> 0  1
     * 此图表示存在4个顶点组成的图
     * 顶点id分别是0,1,2,3,4
     * 列表表示每个顶点与其他所有顶点也包括自身是否相连通的关系
     * 其中 0,1索引的元素互通 - 双向
     * 2通3 但是 3不通2 - 单向
     * 3通0并且也通1
     *
     * @param v          顶点数
     * @param isDirected 是否是有向图
     */
    public SparseGraph(int v, boolean isDirected) {
        assert v >= 0;
        this.v = v;
        this.e = 0;
        this.isDirected = isDirected;
        //noinspection unchecked
        this.g = (ArrayList<Integer>[]) new ArrayList[v];
        for (int i = 0; i < v; i++) {
            this.g[i] = new ArrayList<>();
        }
    }

    /**
     * 图的顶点数
     *
     * @return
     */
    public int v() {
        return this.v;
    }

    /**
     * 图的边数
     *
     * @return
     */
    public int e() {
        return this.e;
    }

    public void addEdge(int m, int n) {
        assert (m >= 0 && m < this.v) && (n >= 0 && n < this.v);
        // 允许有向图和自换图
        // if (hasEdge(m, n)) {
        //    return;
        // }
        g[m].add(n); // 单向 - 可以添加自身 形成自环图
        if (m != n && !this.isDirected) { // 双向（无向）
            g[n].add(m);
        }
        this.e++;
    }

    public boolean hasEdge(int m, int n) {
        assert (m >= 0 && m < this.v) && (n >= 0 && n < this.v);
        ArrayList<Integer> targets = this.g[m];
        for (Integer target : targets) {
            if (target == n) return true;
        }
        return false;
    }

    /**
     * 通过顶点遍历邻边
     * @param vertex
     * @return
     */
    public ArrayList<Integer> getEdgesByVertex(int vertex){
        return this.g[vertex];
    }

    // TODO testing method to be deleted
    public void testPrint() {
        // 打印所有元素的邻边
        for (int i = 0; i < v; i++) {
            System.out.println(i +" --> "+ getEdgesByVertex(i).toString());
        }
    }

    public static void main(String[] args) {
        // 无向图 = 双向图
        SparseGraph f = new SparseGraph(4, false);
        f.addEdge(0, 2);
        f.addEdge(1, 3);
        f.testPrint();

        System.out.println("================");
        // 有向图 = 单向图
        SparseGraph t = new SparseGraph(4, true);
        t.addEdge(0, 2);
        t.addEdge(1, 0);
        t.addEdge(1, 1);
        t.addEdge(1, 2);
        t.addEdge(1, 3);
        t.testPrint();
        ArrayList<Integer> edges = t.getEdgesByVertex(1);
        System.out.println(edges.toString());
    }
}
